/*
 * Longest Common Substring
 *
 * Give two strings X={x1,x2,...xm} and Y={y1,y2,...yn}. We need to figure out three cases.
 * 1. If xm==yn, then we continue to find the LCS in Xm-1, Yn-1.
 * 2. If xm1=yn, then we need to find LCS on Xm-1, Y or X, Yn-1.
 *
 * The equations are as follows:
 * C[i,j] = 0                                if i=0 or j=0;
 *        = C[i-1,j-1] + 1                   if i,j>0 and xi==yj;
 *        = max{C[i-1,j], C[i,j-1]}          if i,j>0 and xi!=yj;
 *
 */

#include <iostream>
using namespace std;

void LCS_length(char *x, char *y, int lenX, int lenY)
{
	// Initialize 2-dim array.
	int ** c = new int *[lenX+1];	// optimal value
	int ** s = new int *[lenX+1];   // solution
	int i,j;
	for(i=0;i<=lenY;i++)
	{
		c[i] = new int[lenY+1];
		s[i] = new int[lenY+1];
	}

	// Set col 1 and row 1 as 0;
	for(i=0;i<=lenX;i++)
	{
		c[i][0] = 0;	
	}
	for(i=0;i<=lenY;i++)
	{
		c[0][i] = 0;
	}

	// dynamic programming to find the optimal solution for above equation.

	for(i=1;i<=lenX;i++)
	{
		for(j=1;j<=lenY;j++)
		{
			if(x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1]+1;
				// do something in s[i][j] to indicate direction
			}
			else
			{
				if(c[i-1][j] < c[i][j-1])
				  c[i][j] = c[i][j-1];
				// do something in s[i][j]
				else
				  c[i][j] = c[i-1][j];
				// do something in s[i][j]
			}
		}
	}

}



int main()
{
	char X[]={'A','B','C','B','D','A','B'};
	char Y[]={'B','D','C','A','B','A'};
	LCS_length(X,Y,7,6);
	return 0;
}
